import {Node, LinkedList} from './linked_list'

export class DoublyNode extends Node {
  constructor(ele) {
    super(ele);
    this.prev = null;
  }
}

export class DoublyLinkedList extends LinkedList {
  constructor() {
    super();
    this.tail = null;
  }

  // 1. 索引方法
  // 1.1 返回链表中特定位置的元素。如果链表中不存在这样的元素，则返回undefined
  // 改进：如果 position > length/2, 则从尾部进行遍历
  getElement(position) {
    if (position >= 0 && position < this.length) {
      let current = this.head;
      if (position < this.length / 2) {
        for (let i = 0; i < position; i++) {
          current = current.next;
        }
      } else {
        current = this.tail;
        for (let i = this.length - 1; i > position; i--) {
          current = current.prev;
        }
      }

      return current;
    }
    return undefined;
  }

  // 2. 插入元素
  // 2.1 在链表尾部插入元素
  // - this.tail 指向插入元素
  // - 插入元素.prev 指向之前的this.tail
  push(element) {
    if (element == undefined) return false;

    const doubleNode = new DoublyNode(element);
    if (this.isEmpty()) {
      this.head = doubleNode;
    } else {
      const tail = this.tail;
      tail.next = doubleNode;
      doubleNode.prev = tail;
    }
    this.tail = doubleNode;
    this.length++;
    return true;
  }

  // 2.2 在链表特定位置插入元素
  // - 插入元素多一个.prev指向
  insert(element, position) {
    if (element == undefined) return false;

    if (position >= 0 && position <= this.length) {
      const doubleNode = new DoublyNode(element);
      let current = this.head;
      if (position === 0) {
        this.head = doubleNode;
        doubleNode.next = current;
        current.prev = doubleNode;
      } else if (position === this.length) {
        return this.push(element);
      } else {
        current = this.getElement(position);
        const prev = current.prev;

        doubleNode.prev = prev;
        prev.next = doubleNode;
        doubleNode.next = current;
        current.prev = doubleNode;
      }

      this.length++;
      return true;
    }

    return false;
  }

  // 3. 移除元素

  // 3.1 删除第一个元素
  shift() {
    if (this.isEmpty()) return false;

    const len = this.getSize();
    if (len === 1) {
      this.head = null;
      this.tail = null;
    } else {
      this.head = this.head.next;
      this.head.prev = null;
    }
    this.length--;
    return true;
  }
  // 3.2 删除最后一个元素
  pop() {
    if (this.isEmpty()) return false;
    const len = this.getSize();

    if (len === 1) {
      return this.shift();
    } else {
      this.tail = this.tail.prev;
      this.tail.next = null;
    }
    this.length--;
    return true;
  }
  // 3.3 移除特定位置的元素
  // 改：被移除元素后面的元素.prev 指向被移除元素前面的元素
  removeAt(position) {
    if (position >= 0 && position < this.length) {
      if (position === 0) return this.shift();
      const len = this.length;
      if (position === len - 1) return this.pop();

      const current = this.getElement(position);
      const prev = current.prev;
      const next = current.next;
      prev.next = next;
      next.prev = prev;

      this.length--;
      return true;
    }
    return false;
  }
}
